\begin{usection}{11003. Boxes}
	\url{http://uva.onlinejudge.org/external/110/11003.html}\\
	
	Dada una secuencia de cajas (cada una tiene cierto peso y soporta cierta carga), se quiere encontrar la subsecuencia de cajas más larga que se puedan apilar en ese orden. La pila tiene que cumplir que ninguna caja tenga más peso encima de lo que soporta.
	
	\begin{usubsection}{Idea}
		Este problema lo resolvimos con un algoritmo goloso. Se basa en construir, para una altura dada, la torre de esa altura que más peso soporte encima de ella. (Entiendase que la torre que soporta más peso es la que tiene $min(max\_load-\sum_{c\in \mbox{cajas apiladas encima}} peso(c))$ máximo)
			
		Para esto tenemos $n$ torres, donde la torre $k$ tiene altura $k$ y es la que más peso soporta de todas las posibles de esa altura.
		Para cada caja nueva, modifico las torres que tenia de la siguiente manera: La torre de altura $k$ que más peso soporta es la mejor entre la que ya tenía y la torre producida al apilar la caja nueva sobre la torre de altura $k-1$.
			(Los $k$ para los cuales no existe una torre tienen un valor negativo).
			
		Así, la torre de altura máxima que puedo formar es la más alta de los que tienen valor positivo ($\geq 0$) cuando procesé todas las cajas.
	\end{usubsection}
	
	\begin{usubsection}{Complejidad}
		Para cada caja, el algoritmo tiene que actualizar todas las torres. Comparar y actualizar una torre cuesta \Ode{1}. Observese que para la caja $i$ solo es necesario actualizar las torres 1 a $i$, porque las demás son imposibles.
		Entonces la complejidad es de $\sum_{i=0}^n i \in \Ode{n^2}$.
		Se puede ver claramente en el algoritmo la cantidad de operaciones porque es de la forma:
		\begin{pseudo}
			\FOR $i\gets 1 \TO n$\\
			\tab \FOR $k\gets i \TO 0$
		\end{pseudo}
	\end{usubsection}
\end{usection}


